package com.example.algorithm.no0088.solution;

import com.example.algorithm.no0088.Solution;

import java.util.Arrays;

/**
 * @Description 解答-合并两个有序数组
 * 双指针 / 从前往后
 * 一般而言，对于有序数组可以通过 双指针法 达到O(n + m)的时间复杂度
 * 时间复杂度 : O(n+m)。
 * 空间复杂度 : O(m)。
 * @ClassName MapSolution
 * @Author Administrator
 * @Date 2020/5/20 10:26
 * @Version 1.0.0
 */
public class SolutionImpl1 implements Solution {
    @Override
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Make a copy of nums1.
        int [] nums1_copy = new int[m];
        System.arraycopy(nums1, 0, nums1_copy, 0, m);

        // Two get pointers for nums1_copy and nums2.
        int p1 = 0;
        int p2 = 0;

        // Set pointer for nums1
        int p = 0;

        // Compare elements from nums1_copy and nums2
        // and add the smallest one into nums1.
        while ((p1 < m) && (p2 < n)) {
            nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];
        }

        // if there are still elements to add
        if (p1 < m) {
            System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
        }
        if (p2 < n) {
            System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
        }
    }
}
